//
// Created by Administrator on 2021/6/24.
//
//给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;;

class Solution { // 题解
/**
 * 一条直线可以用 y = kx + b 表示,即k b 两个数值表征了一条直线
 * 考察一个点和另外所有点构成直线的斜率 找最多相同的
 */
public:
    /**
     * 求a b 的最大公约数
     * @param a
     * @param b
     * @return
     */
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }

    int maxPoints(vector<vector<int>> &points) {
        int n = points.size();
        // 如果只有两个点,直接返回点数
        if (n <= 2) {
            return n;
        }
        int ret = 0;
        // 第一次遍历所有点
        for (int i = 0; i < n; i++) {
            /**
             * 当我们找到一条直线经过了图中超过半数的点时，我们即可以确定该直线即为经过最多点的直线；
               当我们枚举到点 i（假设编号从 0 开始）时，我们至多只能找到n−i个点共线。
               假设此前找到的共线的点的数量的最大值为 kk，如果有 k≥n−i，
               那么此时我们即可停止枚举，因为不可能再找到更大的答案了。
             */
            if (ret >= n - i || ret > n / 2) {
                break;
            }
            unordered_map<int, int> mp;
            // 第二个遍历
            for (int j = i + 1; j < n; j++) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(abs(x), abs(y));
                    x /= gcdXY, y /= gcdXY;
                }
                mp[y + x * 20001]++;
            }
            int maxn = 0;
            for (auto&[_, num] : mp) {
                maxn = max(maxn, num + 1);
            }
            ret = max(ret, maxn);
        }
        return ret;
    }
};


int main() {
    vector<vector<int>> points{{1, 1},
                               {2, 2},
                               {3, 3}};
    Solution sol;
    cout << sol.maxPoints(points) << endl;
    return 0;
}